package DP;

/**
 * @author chenhong
 * @version 1.0
 * @description TODO
 * @date 2023/4/18 22:50
 */
public class L300 {
    public static void main(String[] args) {
        L300 l300 = new L300();
        System.out.println(l300.lengthOfLIS(new int[]{10,9,2,5,3,7,101,18}));

    }

    public int lengthOfLIS(int[] nums) {
        if (nums.length == 1)
            return 1;
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int ans = 1;
        for (int i = 1; i < nums.length; i++) {
            if(nums[i] == nums[i - 1])
                dp[i] = dp[i-1];
            else {
                dp[i] = 1;
                for (int j = 0; j < i; j++) {
                    if (nums[i] == nums[j]) {
                        dp[i] = Math.max(dp[i], dp[j]);
                    } else if (nums[i] > nums[j]) {
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                    }
                }
            }


            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }
}
